#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <numeric>

using namespace std;
class DSU
{
private:
    vector<int> parent;
    int components;

public:
    DSU(int n)
    {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        components = n;
    }

    int find(int i)
    {
        if (parent[i] == i)
        {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    void unite(int i, int j)
    {
        int fi = find(i);
        int fj = find(j);
        if (fi != fj)
        {
            parent[fi] = fj;
            components--;
        }
    }

    int getComponents() const
    {
        return components;
    }
};
class Solution
{
public:
    int minCost(int n, vector<vector<int>> &edges, int k)
    {
        unordered_set<int> weightsSet;
        sort(edges.begin(), edges.end(), [&weightsSet](const vector<int> &x, const vector<int> &y)
             { return x[2] < y[2]; });
        for(auto edge:edges){
             weightsSet.insert(edge[2]);
        }
        int ans = *max_element(weightsSet.begin(), weightsSet.end()), nE = edges.size();
        int l = 0, r = nE;
        if(k >= n){return 0;}
        // 二分edges
        while (l < r)
        {
            int mid = ((r - l) >> 1) + l;
            int weight = edges[mid][2];

            DSU dsu = DSU(n);

            for(int i = 0; i <= mid; ++i){
                int u = edges[i][0], v = edges[i][1];
                dsu.unite(u,v);
            }
            if(dsu.getComponents() <= k){
                ans = min(weight, ans);
                r = mid;
            }
            else{
                l = mid + 1;
            }
        }
        return ans;
    }
};

